//
// Created by zhulingfeng on 2020/4/12.
//

#include <gtest/gtest.h>
#include <depth_first_search/subsets.hpp>
#include "utils/utils.hpp"
class SubsetsTest : public ::testing::Test {};
using vec2d = std::vector<std::vector<int>>;

/**
 * @brief Compare if two subsets are equal, it need each subset in order, e.g
 * . {1,2} and {1,2} is ok, but {1,2} and {2,1} is not ok.
 * @param input1
 * @param input2
 * @return
 */
bool SubsetsEqual(vec2d& input1, vec2d& input2) {
  if (input1.size() != input2.size()) return false;
  std::vector<bool> matched(input1.size(), false);
  for (int i = 0; i < input1.size(); ++i) {
    bool find = false;
    for (int j = 0; j < input2.size(); ++j) {
      if (matched[j]) continue;
      if (std::equal(input1[i].begin(), input1[i].end(), input2[j].begin())) {
        find = true;
        matched[j] = true;
        break;
      } else {
        // PrintVec("not found: input1: ", input1[i]);
        // PrintVec("not found: input2: ", input2[j]);
      }
    }
    if (!find) {
      // PrintVec("not found: input1: ", input1[i]);
      return false;
    }
  }
  return true;
}
TEST_F(SubsetsTest, TestSubsetsWithoutDuplicates) {
  vec2d inputs = {{}, {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}};
  std::vector<vec2d> gts = {
      {{}},
      {{}, {1}},
      {{}, {1}, {2}, {1, 2}},
      {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}},
      {{},
       {1},
       {2},
       {3},
       {4},
       {1, 2},
       {1, 3},
       {1, 4},
       {2, 3},
       {2, 4},
       {3, 4},
       {1, 2, 3},
       {1, 2, 4},
       {1, 3, 4},
       {2, 3, 4},
       {1, 2, 3, 4}}};
  assert(inputs.size() == gts.size());
  for (int i = 0; i < inputs.size(); i++) {
    auto output = Subsets(inputs[i]);
    bool equal = SubsetsEqual(output, gts[i]);
    if (!equal) {
      std::cout << std::endl;
      PrintVec("input", inputs[i]);
      PrintVec2d("output", output);
      PrintVec2d("expected", gts[i]);
    }
    EXPECT_TRUE(equal);
  }
}

TEST_F(SubsetsTest, TestSubsetsWithDuplicates) {
  vec2d inputs = {{}, {1}, {1, 1}, {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, {2, 1, 2}};
  std::vector<vec2d> gts = {{{}},
                            {{}, {1}},
                            {{}, {1}, {1, 1}},
                            {{}, {1}, {1, 1}, {1, 1, 1}},
                            {{}, {1}, {2}, {1, 1}, {1, 2}, {1, 1, 2}},
                            {{}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}},
                            {{}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}}};
  assert(inputs.size() == gts.size());
  for (int i = 0; i < inputs.size(); i++) {
    auto output = SubsetsWithDup(inputs[i]);
    bool equal = SubsetsEqual(output, gts[i]);
    if (!equal) {
      std::cout << std::endl;
      PrintVec("input", inputs[i]);
      PrintVec2d("output", output);
      PrintVec2d("expected", gts[i]);
    }
    EXPECT_TRUE(equal);
  }
}
